package Simple4;
import java.util.HashSet;

public class AllStringSetsIdentical {
	
	/**
	 * A java method takes an array of sets of String object, determine wheter
	 * all sets in the array are equivalent.
	 * Time complexity: if sets[M][N]----O(M*N)
	 * 
	 * @param sets	a sets of String object
	 * @return		true --if the all the are equivalent.
	 * 				false --if not
	 */
	public static boolean allStringSetsIdentical(String[][] sets){
		//edge case
		if(sets==null || sets.length==0) return false;
		
		//key is the string, avoid duplicate
		HashSet<String> my_set = new HashSet<String>();
		for(int i=0;i<sets[0].length;++i){
			my_set.add(sets[0][i]);
		}
		
		//check equivalent.
		for(int i=1;i<sets.length;++i){
			HashSet<String> set_clone = new HashSet<String>(my_set);
			for(int j=0;j<sets[i].length;++j){
				String temp = sets[i][j];
				//here is no such word or 
				if(!my_set.contains(temp))
					return false;
				//delete current word from clone set
				else{
					set_clone.remove(temp);
				}
			}
			//if here is something left in set, then it's not equivalent
			if(!set_clone.isEmpty())
				return false;
		}
		//no false case occur, return true.
		return true;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(allStringSetsIdentical
					(new String[][] {{"a","b"},{"b","b","a"},{"b","a"}}));
		System.out.println(allStringSetsIdentical
					(new String[][] {{"a","b"},{"a"},{"b"}}));
	}

}
